SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Karatsuba algorithm</title>

</head>

Karatsuba algorithm

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><table class="infobox"><caption class="infobox-title">Karatsuba algorithm</caption><tbody><tr><th scope="row" class="infobox-label">Class</th><td class="infobox-data"><a href="Multiplication_algorithm" title="Multiplication algorithm">Multiplication algorithm</a></td></tr></tbody></table>

The Karatsuba algorithm is a fast <a href="Multiplication_algorithm" title="Multiplication algorithm">multiplication algorithm</a> for <a href="Integer" title="Integer">integers</a>. It was discovered by <a href="Anatoly_Karatsuba" title="Anatoly Karatsuba">Anatoly Karatsuba</a> in 1960 and published in 1962.<a href="#cite_note-kara1962-1">[1]</a><a href="#cite_note-kara1995-2">[2]</a><a href="#cite_note-knuthV2-3">[3]</a> It is a <a href="Divide-and-conquer_algorithm" title="Divide-and-conquer algorithm">divide-and-conquer algorithm</a> that reduces the multiplication of two n-digit numbers to three multiplications of n/2-digit numbers and, by repeating this reduction, to at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{\log _{2}3}\approx n^{1.58}}">

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{\log _{2}3}\approx n^{1.58}}</annotation>

</semantics>

</math><img src="./513d063dc093e12ff06009c8f6fbd2e2dca2949c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:13.418ex; height:2.676ex;" alt="{\displaystyle n^{\log _{2}3}\approx n^{1.58}}" loading="lazy"> single-digit multiplications. It is therefore <a href="Asymptotic_complexity" class="mw-redirect" title="Asymptotic complexity">asymptotically faster</a> than the <a href="Long_multiplication" class="mw-redirect" title="Long multiplication">traditional</a> algorithm, which performs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{2}}</annotation>

</semantics>

</math><img src="./ac9810bbdafe4a6a8061338db0f74e25b7952620.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.449ex; height:2.676ex;" alt="{\displaystyle n^{2}}" loading="lazy"> single-digit products.

The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm.

The <a href="Toom%E2%80%93Cook_multiplication" title="Toom–Cook multiplication">Toom–Cook algorithm</a> (1963) is a faster generalization of Karatsuba's method, and the <a href="Sch%C3%B6nhage%E2%80%93Strassen_algorithm" title="Schönhage–Strassen algorithm">Schönhage–Strassen algorithm</a> (1971) is even faster, for sufficiently large n.

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

The standard procedure for multiplication of two n-digit numbers requires a number of elementary operations proportional to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{2}\,\!}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{2}\,\!}</annotation>

</semantics>

</math><img src="./66e4978ce5a3d3abcba9a409a9b4a7de47715e72.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-right: -0.387ex; width:2.836ex; height:2.676ex;" alt="{\displaystyle n^{2}\,\!}" loading="lazy">, or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})\,\!}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{2})\,\!}</annotation>

</semantics>

</math><img src="./08ff1eae47b9a08f9c1b1138243813d0b57270a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-right: -0.387ex; width:6.419ex; height:3.176ex;" alt="{\displaystyle O(n^{2})\,\!}" loading="lazy"> in <a href="Big-O_notation" class="mw-redirect" title="Big-O notation">big-O notation</a>. <a href="Andrey_Kolmogorov" title="Andrey Kolmogorov">Andrey Kolmogorov</a> conjectured that the traditional algorithm was <a href="Asymptotically_optimal" class="mw-redirect" title="Asymptotically optimal">asymptotically optimal</a>, meaning that any algorithm for that task would require <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (n^{2})\,\!}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (n^{2})\,\!}</annotation>

</semantics>

</math><img src="./5cf05ff7c4074ab7cc50343cbf586bc6550dc9f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-right: -0.387ex; width:6.323ex; height:3.176ex;" alt="{\displaystyle \Omega (n^{2})\,\!}" loading="lazy"> elementary operations.

In 1960, Kolmogorov organized a seminar on mathematical problems in <a href="Cybernetics" title="Cybernetics">cybernetics</a> at the <a href="Moscow_State_University" title="Moscow State University">Moscow State University</a>, where he stated the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (n^{2})\,\!}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (n^{2})\,\!}</annotation>

</semantics>

</math><img src="./5cf05ff7c4074ab7cc50343cbf586bc6550dc9f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-right: -0.387ex; width:6.323ex; height:3.176ex;" alt="{\displaystyle \Omega (n^{2})\,\!}" loading="lazy"> conjecture and other problems in the <a href="Computational_complexity_theory" title="Computational complexity theory">complexity of computation</a>. Within a week, Karatsuba, then a 23-year-old student, found an algorithm that multiplies two n-digit numbers in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{\log _{2}3})}">

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{\log _{2}3})}</annotation>

</semantics>

</math><img src="./770c7081e94ce7027c145a2f892341605e9b0272.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.352ex; height:3.176ex;" alt="{\displaystyle O(n^{\log _{2}3})}" loading="lazy"> elementary steps, thus disproving the conjecture. Kolmogorov was very excited about the discovery; he communicated it at the next meeting of the seminar, which was then terminated. Kolmogorov gave some lectures on the Karatsuba result at conferences all over the world (see, for example, "Proceedings of the International Congress of Mathematicians 1962", pp. 351–356, and also "6 Lectures delivered at the International Congress of Mathematicians in Stockholm, 1962") and published the method in 1962, in the <a href="Proceedings_of_the_USSR_Academy_of_Sciences" title="Proceedings of the USSR Academy of Sciences">Proceedings of the USSR Academy of Sciences</a>. The article had been written by Kolmogorov and contained two results on multiplication, Karatsuba's algorithm and a separate result by <a href="Yuri_Petrovich_Ofman" class="mw-redirect" title="Yuri Petrovich Ofman">Yuri Ofman</a>; it listed "A. Karatsuba and Yu. Ofman" as the authors. Karatsuba only became aware of the paper when he received the reprints from the publisher.<a href="#cite_note-kara1995-2">[2]</a>

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Basic_step">Basic step</h3></div>

The basic principle of Karatsuba's algorithm is <a href="Divide-and-conquer_algorithm" title="Divide-and-conquer algorithm">divide-and-conquer</a>, using a formula that allows one to compute the product of two large numbers <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> using three multiplications of smaller numbers, each with about half as many digits as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">, plus some additions and digit shifts. This basic step is, in fact, a generalization of <a href="Multiplication_algorithm#Complex_number_multiplication" title="Multiplication algorithm">a similar complex multiplication algorithm</a>, where the <a href="Imaginary_unit" title="Imaginary unit">imaginary unit</a> i is replaced by a power of the <a href="Radix" title="Radix">base</a>.

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> be represented as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-digit strings in some base <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy">. For any positive integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> less than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, one can write the two given numbers as

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x=x_{1}B^{m}+x_{0},}</annotation>

</semantics>

</math><img src="./f715fe938ce8828933a09cdf6b13635e71593dc5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.122ex; height:2.676ex;" alt="{\displaystyle x=x_{1}B^{m}+x_{0},}" loading="lazy"></dd>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y=y_{1}B^{m}+y_{0},}</annotation>

</semantics>

</math><img src="./95bc8c6338aedaccf47919247690d0ae37d6a3b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.567ex; height:2.676ex;" alt="{\displaystyle y=y_{1}B^{m}+y_{0},}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{0}}</annotation>

</semantics>

</math><img src="./86f21d0e31751534cd6584264ecf864a6aa792cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{0}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{0}}</annotation>

</semantics>

</math><img src="./6d943dbbb0b56ca750c4d62c5b54b4ae29a773da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.193ex; height:2.009ex;" alt="{\displaystyle y_{0}}" loading="lazy"> are less than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B^{m}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B^{m}}</annotation>

</semantics>

</math><img src="./373e4ac701258dd693c81290941e604d93a28fd9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.439ex; height:2.343ex;" alt="{\displaystyle B^{m}}" loading="lazy">. The product is then

<mtr>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}xy&=(x_{1}B^{m}+x_{0})(y_{1}B^{m}+y_{0})\\&=x_{1}y_{1}B^{2m}+(x_{1}y_{0}+x_{0}y_{1})B^{m}+x_{0}y_{0}\\&=z_{2}B^{2m}+z_{1}B^{m}+z_{0},\\\end{aligned}}}</annotation>

</semantics>

</math><img src="./e01a975655d41538eb322588f5c8ca3ab24ed6bf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.171ex; width:42.675ex; height:9.509ex;" alt="{\displaystyle {\begin{aligned}xy&=(x_{1}B^{m}+x_{0})(y_{1}B^{m}+y_{0})\\&=x_{1}y_{1}B^{2m}+(x_{1}y_{0}+x_{0}y_{1})B^{m}+x_{0}y_{0}\\&=z_{2}B^{2m}+z_{1}B^{m}+z_{0},\\\end{aligned}}}" loading="lazy">

where

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z_{2}=x_{1}y_{1},}</annotation>

</semantics>

</math><img src="./a7a515d0539482252862a59ff5005568ee66a56b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.458ex; height:2.009ex;" alt="{\displaystyle z_{2}=x_{1}y_{1},}" loading="lazy"></dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z_{1}=x_{1}y_{0}+x_{0}y_{1},}</annotation>

</semantics>

</math><img src="./19997bfdbf187fc8a8c3e6e0a9ff8294d19bf882.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.876ex; height:2.343ex;" alt="{\displaystyle z_{1}=x_{1}y_{0}+x_{0}y_{1},}" loading="lazy"></dd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z_{0}=x_{0}y_{0}.}</annotation>

</semantics>

</math><img src="./275e9f651331408fa0a4cbe6426f91c8a3f12601.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.458ex; height:2.009ex;" alt="{\displaystyle z_{0}=x_{0}y_{0}.}" loading="lazy"></dd></dl>

These formulae require four multiplications and were known to <a href="Charles_Babbage" title="Charles Babbage">Charles Babbage</a>.<a href="#cite_note-4">[4]</a> Karatsuba observed that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle xy}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle xy}</annotation>

</semantics>

</math><img src="./c72eb345e496513fb8b2fa4aa8c4d89b855f9a01.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.485ex; height:2.009ex;" alt="{\displaystyle xy}" loading="lazy"> can be computed in only three multiplications, at the cost of a few extra additions. With <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z_{0}}</annotation>

</semantics>

</math><img src="./9e72d1d86e86355892b39b8eb32b964834e113bf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.135ex; height:2.009ex;" alt="{\displaystyle z_{0}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z_{2}}</annotation>

</semantics>

</math><img src="./5abf655fa14f7ea44ad0ca781b59ff59c5f49117.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.135ex; height:2.009ex;" alt="{\displaystyle z_{2}}" loading="lazy"> as before and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z_{3}=(x_{1}+x_{0})(y_{1}+y_{0}),}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z_{3}=(x_{1}+x_{0})(y_{1}+y_{0}),}</annotation>

</semantics>

</math><img src="./897e711ebd325805bf0f7a1f3c1b8420f88c4fdf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.335ex; height:2.843ex;" alt="{\displaystyle z_{3}=(x_{1}+x_{0})(y_{1}+y_{0}),}" loading="lazy"> one can observe that

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}z_{1}&=x_{1}y_{0}+x_{0}y_{1}\\&=(x_{1}+x_{0})(y_{0}+y_{1})-x_{1}y_{1}-x_{0}y_{0}\\&=z_{3}-z_{2}-z_{0}.\\\end{aligned}}}</annotation>

</semantics>

</math><img src="./261e76e8ebce4df162cb0195ef35fba3ea0488f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.838ex; width:39.275ex; height:8.843ex;" alt="{\displaystyle {\begin{aligned}z_{1}&=x_{1}y_{0}+x_{0}y_{1}\\&=(x_{1}+x_{0})(y_{0}+y_{1})-x_{1}y_{1}-x_{0}y_{0}\\&=z_{3}-z_{2}-z_{0}.\\\end{aligned}}}" loading="lazy"></dd></dl>

Thus only three multiplications are required for computing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z_{0},z_{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z_{0},z_{1}}</annotation>

</semantics>

</math><img src="./217f374ba6e16dcac6a8d8aa07ec311153a53216.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.305ex; height:2.009ex;" alt="{\displaystyle z_{0},z_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z_{2}.}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z_{2}.}</annotation>

</semantics>

</math><img src="./04311a5ef8f6411bf3e4ddf13ed73ea730397909.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.782ex; height:2.009ex;" alt="{\displaystyle z_{2}.}" loading="lazy">

<div class="mw-heading mw-heading3"><h3 id="Example">Example</h3></div>

To compute the product of 12345 and 6789, where B = 10, choose m = 3. We use m right shifts for decomposing the input operands using the resulting base (Bm = 1000), as:

Only three multiplications, which operate on smaller integers, are used to compute three partial results:

We get the result by just adding these three partial results, shifted accordingly (and then taking carries into account by decomposing these three inputs in base 1000 as for the input operands):

<dl><dd>result = z2 · (Bm)2 + z1 · (Bm)1 + z0 · (Bm)0, i.e.</dd>

<dd>result = 72 · 10002 + 11538 · 1000 + 272205 = 83810205.</dd></dl>

Note that the intermediate third multiplication operates on an input domain which is less than two times larger than for the two first multiplications, its output domain is less than four times larger, and base-1000 carries computed from the first two multiplications must be taken into account when computing these two subtractions.

<div class="mw-heading mw-heading3"><h3 id="Recursive_application">Recursive application</h3></div>

If n is four or more, the three multiplications in Karatsuba's basic step involve operands with fewer than n digits. Therefore, those products can be computed by <a href="Recursion" title="Recursion">recursive</a> calls of the Karatsuba algorithm. The recursion can be applied until the numbers are so small that they can (or must) be computed directly.

In a computer with a full 32-bit by 32-bit <a href="Binary_multiplier" title="Binary multiplier">multiplier</a>, for example, one could choose B = 231 and store each digit as a separate 32-bit binary word. Then the sums x1 + x0 and y1 + y0 will not need an extra binary word for storing the carry-over digit (as in <a href="Carry-save_adder" title="Carry-save adder">carry-save adder</a>), and the Karatsuba recursion can be applied until the numbers to multiply are only one digit long.

<div class="mw-heading mw-heading3"><h3 id="Time_complexity_analysis"><a href="Time_complexity" title="Time complexity">Time complexity</a> analysis</h3></div>

Karatsuba's basic step works for any base B and any m, but the recursive algorithm is most efficient when m is equal to n/2, rounded up. In particular, if n is 2k, for some integer k, and the recursion stops only when n is 1, then the number of single-digit multiplications is 3k, which is nc where c = log23.

Since one can extend any inputs with zero digits until their length is a power of two, it follows that the number of elementary multiplications, for any n, is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 3^{\lceil \log _{2}n\rceil }\leq 3n^{\log _{2}3}\,\!}">

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 3^{\lceil \log _{2}n\rceil }\leq 3n^{\log _{2}3}\,\!}</annotation>

</semantics>

</math><img src="./648b4687b216b4b06aef7b59f69d068b0b62977e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; margin-right: -0.387ex; width:17.578ex; height:3.009ex;" alt="{\displaystyle 3^{\lceil \log _{2}n\rceil }\leq 3n^{\log _{2}3}\,\!}" loading="lazy">.

Since the additions, subtractions, and digit shifts (multiplications by powers of B) in Karatsuba's basic step take time proportional to n, their cost becomes negligible as n increases. More precisely, if T(n) denotes the total number of elementary operations that the algorithm performs when multiplying two n-digit numbers, then

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(n)=3T(\lceil n/2\rceil )+cn+d}</annotation>

</semantics>

</math><img src="./bb210069c9ede32a753ea7d163021aec3a18f0cb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.629ex; height:2.843ex;" alt="{\displaystyle T(n)=3T(\lceil n/2\rceil )+cn+d}" loading="lazy"></dd></dl>

for some constants c and d. For this <a href="Recurrence_relation" title="Recurrence relation">recurrence relation</a>, the <a href="Master_theorem_(analysis_of_algorithms)" title="Master theorem (analysis of algorithms)">master theorem for divide-and-conquer recurrences</a> gives the <a href="Big_O_notation" title="Big O notation">asymptotic</a> bound <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T(n)=\Theta (n^{\log _{2}3})\,\!}">

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(n)=\Theta (n^{\log _{2}3})\,\!}</annotation>

</semantics>

</math><img src="./89d22e9a7228e7dd7b17bb81800adcda2ebbc724.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-right: -0.387ex; width:17.712ex; height:3.176ex;" alt="{\displaystyle T(n)=\Theta (n^{\log _{2}3})\,\!}" loading="lazy">.

It follows that, for sufficiently large n, Karatsuba's algorithm will perform fewer shifts and single-digit additions than longhand multiplication, even though its basic step uses more additions and shifts than the straightforward formula. For small values of n, however, the extra shift and add operations may make it run slower than the longhand method.

<div class="mw-heading mw-heading2"><h2 id="Implementation">Implementation</h2></div>

Here is the pseudocode for this algorithm, using numbers represented in base ten. For the binary representation of integers, it suffices to replace everywhere 10 by 2.<a href="#cite_note-5">[5]</a>

The second argument of the split_at function specifies the number of digits to extract from the right: for example, split_at("12345", 3) will extract the 3 final digits, giving: high="12", low="345".

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>function karatsuba(num1, num2)

if (num1 < 10 or num2 < 10)

return num1 × num2 /* fall back to traditional multiplication */

/* Calculates the size of the numbers. */

m = max(size_base10(num1), size_base10(num2))

m2 = floor(m / 2)

/* m2 = ceil (m / 2) will also work */

/* Split the digit sequences in the middle. */

high1, low1 = split_at(num1, m2)

high2, low2 = split_at(num2, m2)

/* 3 recursive calls made to numbers approximately half the size. */

z0 = karatsuba(low1, low2)

z1 = karatsuba(low1 + high1, low2 + high2)

z2 = karatsuba(high1, high2)

return (z2 × 10 ^ (m2 × 2)) + ((z1 - z2 - z0) × 10 ^ m2) + z0

</pre></div>

An issue that occurs when implementation is that the above computation of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{1}+x_{0})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{1}+x_{0})}</annotation>

</semantics>

</math><img src="./3b20a39e24ae01fa352f5d4d0fc40e481b10fc01.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.418ex; height:2.843ex;" alt="{\displaystyle (x_{1}+x_{0})}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (y_{1}+y_{0})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (y_{1}+y_{0})}</annotation>

</semantics>

</math><img src="./57d94fa0624736a08fb3887eb7fd2406ddd20e9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.037ex; height:2.843ex;" alt="{\displaystyle (y_{1}+y_{0})}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z_{1}}</annotation>

</semantics>

</math><img src="./c3621e468231ab352b7caa30bcf0ce9b452241a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.135ex; height:2.009ex;" alt="{\displaystyle z_{1}}" loading="lazy"> may result in overflow (will produce a result in the range <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B^{m}\leq {\text{result}}<2B^{m}}">

<msup>

</mrow>

</msup>

<mtext>result</mtext>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B^{m}\leq {\text{result}}<2B^{m}}</annotation>

</semantics>

</math><img src="./52fea05a74b8a8ff239851c410de5aaca2ec5682.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:19.942ex; height:2.509ex;" alt="{\displaystyle B^{m}\leq {\text{result}}<2B^{m}}" loading="lazy">), which require a multiplier having one extra bit. This can be avoided by noting that

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z_{1}=(x_{0}-x_{1})(y_{1}-y_{0})+z_{2}+z_{0}.}</annotation>

</semantics>

</math><img src="./c60499a221569cb05cf2521f9c543b67bc00874c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:34.286ex; height:2.843ex;" alt="{\displaystyle z_{1}=(x_{0}-x_{1})(y_{1}-y_{0})+z_{2}+z_{0}.}" loading="lazy"></dd></dl>

This computation of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{0}-x_{1})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{0}-x_{1})}</annotation>

</semantics>

</math><img src="./f21ee9a32ce400261d548782721b6aad4b7752ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.418ex; height:2.843ex;" alt="{\displaystyle (x_{0}-x_{1})}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (y_{1}-y_{0})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (y_{1}-y_{0})}</annotation>

</semantics>

</math><img src="./e654ee0439a3e17f5e60c36cd541050fb25139b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.037ex; height:2.843ex;" alt="{\displaystyle (y_{1}-y_{0})}" loading="lazy"> will produce a result in the range of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle -B^{m}<{\text{result}}<B^{m}}">

<msup>

</mrow>

</msup>

<mtext>result</mtext>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -B^{m}<{\text{result}}<B^{m}}</annotation>

</semantics>

</math><img src="./b73b90fadd0d446a1eb44c096122caacc004c2e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:20.587ex; height:2.509ex;" alt="{\displaystyle -B^{m}<{\text{result}}<B^{m}}" loading="lazy">. This method may produce negative numbers, which require one extra bit to encode signedness, and would still require one extra bit for the multiplier. However, one way to avoid this is to record the sign and then use the absolute value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{0}-x_{1})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{0}-x_{1})}</annotation>

</semantics>

</math><img src="./f21ee9a32ce400261d548782721b6aad4b7752ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.418ex; height:2.843ex;" alt="{\displaystyle (x_{0}-x_{1})}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (y_{1}-y_{0})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (y_{1}-y_{0})}</annotation>

</semantics>

</math><img src="./e654ee0439a3e17f5e60c36cd541050fb25139b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.037ex; height:2.843ex;" alt="{\displaystyle (y_{1}-y_{0})}" loading="lazy"> to perform an unsigned multiplication, after which the result may be negated when both signs originally differed. Another advantage is that even though <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x_{0}-x_{1})(y_{1}-y_{0})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x_{0}-x_{1})(y_{1}-y_{0})}</annotation>

</semantics>

</math><img src="./2a5411e3009a09e03b44de0c9de28725ec75363a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.454ex; height:2.843ex;" alt="{\displaystyle (x_{0}-x_{1})(y_{1}-y_{0})}" loading="lazy"> may be negative, the final computation of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z_{1}}</annotation>

</semantics>

</math><img src="./c3621e468231ab352b7caa30bcf0ce9b452241a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.135ex; height:2.009ex;" alt="{\displaystyle z_{1}}" loading="lazy"> only involves additions.

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFA._Karatsuba_and_Yu._Ofman1962" class="citation journal cs1">A. Karatsuba and Yu. Ofman (1962). <a rel="nofollow" class="external text" href="https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=26729&option_lang=eng">"Multiplication of Many-Digital Numbers by Automatic Computers"</a>. Proceedings of the USSR Academy of Sciences. 145: 293–294. Translation in the academic journal <a href="Physics-Doklady" class="mw-redirect" title="Physics-Doklady">Physics-Doklady</a>, 7 (1963), pp. 595–596</cite><code class="cs1-code">{{cite journal}}</code>: CS1 maint: postscript (link)

</li>

<cite id="CITEREFA._A._Karatsuba1995" class="citation journal cs1">A. A. Karatsuba (1995). <a rel="nofollow" class="external text" href="http://www.ccas.ru/personal/karatsuba/divcen.pdf">"The Complexity of Computations"</a> (PDF). Proceedings of the Steklov Institute of Mathematics. 211: 169–183. Translation from Trudy Mat. Inst. Steklova, 211, 186–202 (1995)</cite><code class="cs1-code">{{cite journal}}</code>: CS1 maint: postscript (link)

</li>

Knuth D.E. (1969) <a href="The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art of Computer Programming</a>. v.2. Addison-Wesley Publ.Co., 724 pp.

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> Charles Babbage, Chapter VIII – Of the Analytical Engine, Larger Numbers Treated, <a rel="nofollow" class="external text" href="https://archive.org/details/bub_gb_Fa1JAAAAMAAJ/page/n142">Passages from the Life of a Philosopher</a>, Longman Green, London, 1864; page 125.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFWeiss2005" class="citation book cs1">Weiss, Mark A. (2005). Data Structures and Algorithm Analysis in C++. Addison-Wesley. p. 480. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0321375319</bdi>.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.cs.pitt.edu/~kirk/cs1501/animations/Karatsuba.html">Karatsuba's Algorithm for Polynomial Multiplication</a></li>

<li><cite id="CITEREFWeisstein" class="citation web cs1"><a href="Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/KaratsubaMultiplication.html">"Karatsuba Multiplication"</a>. <a href="MathWorld" title="MathWorld">MathWorld</a>.</cite></li>

<li>Bernstein, D. J., "<a rel="nofollow" class="external text" href="http://cr.yp.to/papers/m3.pdf">Multidigit multiplication for mathematicians</a>". Covers Karatsuba and many other multiplication algorithms.</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Number-theoretic_algorithms413" style="padding:3px"><table class="nowraplinks mw-collapsible uncollapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Number-theoretic_algorithms413" style="font-size:114%;margin:0 4em"><a href="Number_theory" title="Number theory">Number-theoretic</a> <a href="Algorithm" title="Algorithm">algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Primality_test" title="Primality test">Primality tests</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Baillie%E2%80%93PSW_primality_test" title="Baillie–PSW primality test">Baillie–PSW</a></li>

<li><a href="Elliptic_curve_primality" title="Elliptic curve primality">Elliptic curve</a></li>

<li><a href="Pocklington_primality_test" title="Pocklington primality test">Pocklington</a></li>

<li><a href="Fermat_primality_test" title="Fermat primality test">Fermat</a></li>

<li><a href="Lucas_primality_test" title="Lucas primality test">Lucas</a></li>

<li><a href="Lucas%E2%80%93Lehmer_primality_test" title="Lucas–Lehmer primality test">Lucas–Lehmer</a></li>

<li><a href="Lucas%E2%80%93Lehmer%E2%80%93Riesel_test" title="Lucas–Lehmer–Riesel test">Lucas–Lehmer–Riesel</a></li>

<li><a href="Proth's_theorem" title="Proth's theorem">Proth's theorem</a></li>

<li><a href="P%C3%A9pin's_test" title="Pépin's test">Pépin's</a></li>

<li><a href="Quadratic_Frobenius_test" title="Quadratic Frobenius test">Quadratic Frobenius</a></li>

<li><a href="Solovay%E2%80%93Strassen_primality_test" title="Solovay–Strassen primality test">Solovay–Strassen</a></li>

<li><a href="Miller%E2%80%93Rabin_primality_test" title="Miller–Rabin primality test">Miller–Rabin</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Generating_primes" class="mw-redirect" title="Generating primes">Prime-generating</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Sieve_of_Atkin" title="Sieve of Atkin">Sieve of Atkin</a></li>

<li><a href="Sieve_of_Eratosthenes" title="Sieve of Eratosthenes">Sieve of Eratosthenes</a></li>

<li><a href="Sieve_of_Pritchard" title="Sieve of Pritchard">Sieve of Pritchard</a></li>

<li><a href="Sieve_of_Sundaram" title="Sieve of Sundaram">Sieve of Sundaram</a></li>

<li><a href="Wheel_factorization" title="Wheel factorization">Wheel factorization</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Integer_factorization" title="Integer factorization">Integer factorization</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Continued_fraction_factorization" title="Continued fraction factorization">Continued fraction (CFRAC)</a></li>

<li><a href="Dixon's_factorization_method" title="Dixon's factorization method">Dixon's</a></li>

<li><a href="Lenstra_elliptic-curve_factorization" title="Lenstra elliptic-curve factorization">Lenstra elliptic curve (ECM)</a></li>

<li><a href="Euler's_factorization_method" title="Euler's factorization method">Euler's</a></li>

<li><a href="Pollard's_rho_algorithm" title="Pollard's rho algorithm">Pollard's rho</a></li>

<li><a href="Quadratic_sieve" title="Quadratic sieve">Quadratic sieve (QS)</a></li>

<li><a href="General_number_field_sieve" title="General number field sieve">General number field sieve (GNFS)</a></li>

<li><a href="Special_number_field_sieve" title="Special number field sieve">Special number field sieve (SNFS)</a></li>

<li><a href="Rational_sieve" title="Rational sieve">Rational sieve</a></li>

<li><a href="Fermat's_factorization_method" title="Fermat's factorization method">Fermat's</a></li>

<li><a href="Shanks's_square_forms_factorization" title="Shanks's square forms factorization">Shanks's square forms</a></li>

<li><a href="Trial_division" title="Trial division">Trial division</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Multiplication_algorithm" title="Multiplication algorithm">Multiplication</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Ancient_Egyptian_multiplication" title="Ancient Egyptian multiplication">Ancient Egyptian</a></li>

<li><a href="Sch%C3%B6nhage%E2%80%93Strassen_algorithm" title="Schönhage–Strassen algorithm">Schönhage–Strassen</a></li>

<li><a href="F%C3%BCrer's_algorithm" class="mw-redirect" title="Fürer's algorithm">Fürer's</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Euclidean_division" title="Euclidean division">Euclidean</a> <a href="Division_algorithm" title="Division algorithm">division</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Binary_division" class="mw-redirect" title="Binary division">Binary</a></li>

<li><a href="Chunking_(division)" title="Chunking (division)">Chunking</a></li>

<li><a href="Fourier_division" title="Fourier division">Fourier</a></li>

<li><a href="Goldschmidt_division" class="mw-redirect" title="Goldschmidt division">Goldschmidt</a></li>

<li><a href="Newton%E2%80%93Raphson_division" class="mw-redirect" title="Newton–Raphson division">Newton-Raphson</a></li>

<li><a href="Short_division" title="Short division">Short</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Discrete_logarithm" title="Discrete logarithm">Discrete logarithm</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Baby-step_giant-step" title="Baby-step giant-step">Baby-step giant-step</a></li>

<li><a href="Pollard's_rho_algorithm_for_logarithms" title="Pollard's rho algorithm for logarithms">Pollard rho</a></li>

<li><a href="Pollard's_kangaroo_algorithm" title="Pollard's kangaroo algorithm">Pollard kangaroo</a></li>

<li><a href="Pohlig%E2%80%93Hellman_algorithm" title="Pohlig–Hellman algorithm">Pohlig–Hellman</a></li>

<li><a href="Index_calculus_algorithm" title="Index calculus algorithm">Index calculus</a></li>

<li><a href="Function_field_sieve" title="Function field sieve">Function field sieve</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Greatest_common_divisor" title="Greatest common divisor">Greatest common divisor</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Binary_GCD_algorithm" title="Binary GCD algorithm">Binary</a></li>

<li><a href="Euclidean_algorithm" title="Euclidean algorithm">Euclidean</a></li>

<li><a href="Extended_Euclidean_algorithm" title="Extended Euclidean algorithm">Extended Euclidean</a></li>

<li><a href="Lehmer's_GCD_algorithm" title="Lehmer's GCD algorithm">Lehmer's</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quadratic_residue" title="Quadratic residue">Modular square root</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cipolla's_algorithm" title="Cipolla's algorithm">Cipolla</a></li>

<li><a href="Pocklington's_algorithm" title="Pocklington's algorithm">Pocklington's</a></li>

<li><a href="Tonelli%E2%80%93Shanks_algorithm" title="Tonelli–Shanks algorithm">Tonelli–Shanks</a></li>

<li><a href="Berlekamp%E2%80%93Rabin_algorithm" title="Berlekamp–Rabin algorithm">Berlekamp</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other algorithms</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Chakravala_method" title="Chakravala method">Chakravala</a></li>

<li><a href="Cornacchia's_algorithm" title="Cornacchia's algorithm">Cornacchia</a></li>

<li><a href="Exponentiation_by_squaring" title="Exponentiation by squaring">Exponentiation by squaring</a></li>

<li><a href="Integer_square_root" title="Integer square root">Integer square root</a></li>

<li><a href="Integer_relation_algorithm" title="Integer relation algorithm">Integer relation</a> (<a href="Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm" title="Lenstra–Lenstra–Lovász lattice basis reduction algorithm">LLL</a>; <a href="Korkine%E2%80%93Zolotarev_lattice_basis_reduction_algorithm" title="Korkine–Zolotarev lattice basis reduction algorithm">KZ</a>)</li>

<li><a href="Modular_exponentiation" title="Modular exponentiation">Modular exponentiation</a></li>

<li><a href="Montgomery_reduction" class="mw-redirect" title="Montgomery reduction">Montgomery reduction</a></li>

<li><a href="Schoof's_algorithm" title="Schoof's algorithm">Schoof</a></li>

<li><a href="Trachtenberg_system" title="Trachtenberg system">Trachtenberg system</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow hlist" colspan="2"><div>

<ul><li>Italics indicate that algorithm is for numbers of special forms</li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-04" href="https://en.wikipedia.org/wiki/?title=Karatsuba_algorithm&oldid=1288801081">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>